/*
https://leetcode-cn.com/problems/transform-to-chessboard/solution/bian-cheng-qi-pan-by-leetcode/
 */
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution782 {
    public int movesToChessboard(int[][] board) {
        int ans=0;
        Map<String,Integer> map=new HashMap<>();
        int[] nums=new int[board.length];
        int count=0;
        for (int i=0;i<board.length;i++){
            StringBuilder stringBuilder=new StringBuilder();
            for (int j=0;j<board.length;j++){
                stringBuilder.append(board[i][j]);
            }
            String target=stringBuilder.toString();
            if (!valid(target)){
                return -1;
            }
            if (!map.containsKey(target)){
                map.put(target,count);
                count++;
            }
            nums[i]=map.get(target);
        }
        if (map.size()>2){
            return -1;
        }
        if (map.size()==2){
            int c=0;
            for (int i=0;i<board.length;i++){
                if (nums[i]==0){
                    c++;
                }
            }
            if (board.length%2==0){
                if (c!=board.length/2){
                    return -1;
                }
                int p=0;
                int[] oo1=new int[board.length];
                for (int i=0;i<board.length;i++){
                    oo1[i]=p;
                    p=1-p;
                }
                p=1;
                int[] oo2=new int[board.length];
                for (int i=0;i<board.length;i++){
                    oo2[i]=p;
                    p=1-p;
                }
                ans+=Math.min(compare(Arrays.copyOf(nums,nums.length),oo1),compare(Arrays.copyOf(nums,nums.length),oo2));
            }else{
                if (c==board.length/2){
                    int p=1;
                    int[] oo=new int[board.length];
                    for (int i=0;i<board.length;i++){
                        oo[i]=p;
                        p=1-p;
                    }
                    ans+=compare(nums,oo);
                }else if (c==board.length/2+1){
                    int p=0;
                    int[] oo=new int[board.length];
                    for (int i=0;i<board.length;i++){
                        oo[i]=p;
                        p=1-p;
                    }
                    ans+=compare(nums,oo);
                }else {
                    return -1;
                }
            }
        }
        map.clear();
        nums=new int[board.length];
        count=0;
        for (int i=0;i<board.length;i++){
            StringBuilder stringBuilder=new StringBuilder();
            for (int j=0;j<board.length;j++){
                stringBuilder.append(board[j][i]);
            }
            String target=stringBuilder.toString();
            if (!valid(target)){
                return -1;
            }
            if (!map.containsKey(target)){
                map.put(target,count);
                count++;
            }
            nums[i]=map.get(target);
        }
        if (map.size()>2){
            return -1;
        }
        if (map.size()==2){
            int c=0;
            for (int i=0;i<board.length;i++){
                if (nums[i]==0){
                    c++;
                }
            }
            if (board.length%2==0){
                if (c!=board.length/2){
                    return -1;
                }
                int p=0;
                int[] oo1=new int[board.length];
                for (int i=0;i<board.length;i++){
                    oo1[i]=p;
                    p=1-p;
                }
                p=1;
                int[] oo2=new int[board.length];
                for (int i=0;i<board.length;i++){
                    oo2[i]=p;
                    p=1-p;
                }
                ans+=Math.min(compare(Arrays.copyOf(nums,nums.length),oo1),compare(Arrays.copyOf(nums,nums.length),oo2));
            }else{
                if (c==board.length/2){
                    int p=1;
                    int[] oo=new int[board.length];
                    for (int i=0;i<board.length;i++){
                        oo[i]=p;
                        p=1-p;
                    }
                    ans+=compare(nums,oo);
                }else if (c==board.length/2+1){
                    int p=0;
                    int[] oo=new int[board.length];
                    for (int i=0;i<board.length;i++){
                        oo[i]=p;
                        p=1-p;
                    }
                    ans+=compare(nums,oo);
                }else {
                    return -1;
                }
            }
        }
        return ans;
    }

    private boolean valid(String target) {
        int c=0;
        for (char c1 : target.toCharArray()) {
            if (c1=='0'){
                c++;
            }
        }
        if (target.length()%2==0){
            return c==target.length()/2;
        }else{
            return c==target.length()/2 || c==target.length()/2+1;
        }
    }

    private int compare(int[] nums, int[] oo) {
        int ans=0;
        for (int i=0;i<nums.length;i++){
            if (nums[i]!=oo[i]){
                for (int j=i+1;j<nums.length;j++){
                    if (nums[j]!=oo[j] && nums[i]!=nums[j]){
                        nums[i]=1-nums[i];
                        nums[j]=1-nums[j];
                        ans++;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution782().movesToChessboard(new int[][]{{0,0,1,0,1,1},{1,1,0,1,0,0},{1,1,0,1,0,0},{0,0,1,0,1,1},{1,1,0,1,0,0},{0,0,1,0,1,1}}));
    }
}
